package com.lwl.Algorithmic_data_structure.class04归并;


import com.lwl.Algorithmic_data_structure.归并排序.Code01_MergeSort;

/**
 * 归并排序非递归版
 */
public class Code02MergeSortNonRecursive {

    public static void main(String[] args) {
        int testTime = 5000;
        int maxSize = 100;
        int maxValue = 100;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = Code01_MergeSort.generateRandomArray(maxSize, maxValue);
            int[] arr2 = Code01_MergeSort.copyArray(arr1);
            Code01MergeSort.mergeSort(arr1);
            mergeSort(arr2);
            if (!Code01_MergeSort.isEqual(arr1, arr2)) {
                System.out.println("出错了！");
                Code01_MergeSort.printArray(arr1);
                Code01_MergeSort.printArray(arr2);
                break;
            }
        }
        System.out.println("测试结束");
    }

    public static void mergeSort(int[] arr) {
        // 步长，两两比较
        int stepSize = 1;
        int len = arr.length;
        while (stepSize < len) {
            int l = 0;
            while (l < len) {
                // 每次比较的两组：
                // [l , l + stepSize - 1] [l + stepSize , min(l + 2*stepSize - 1 , len - 1)]
                int mid = l + stepSize - 1;
                if (mid >= len) {
                    break;
                }
                int r = Math.min(mid + stepSize, len - 1);
                Code01MergeSort.merge(arr, l, mid, r);
                // 进入下一次两两比较
                l = r + 1;
            }
            // 防止溢出越界
            if (stepSize > len >> 1){
                break;
            }
            // 步长翻倍
            stepSize <<= 1;
        }
    }

}
